home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / oper_sys / deltablu / tstdltbl.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-08-17  |  10.5 KB  |  422 lines
  1. #include <stdio.h>
  2. #include "List.h"
  3. #include "Constraints.h"
  4. #include "DeltaBlue.h"
  5. #include "UsefulConstraints.h"
  6.  
  7. /***************************************************************************
  8.  
  9.     Private Prototypes
  10.  
  11. ****************************************************************************/
  12.  
  13. long MillisecondClock(void);
  14. void Start(void);
  15. void Finish(long*);
  16. void Assign(Variable, long);
  17. void Change(Variable, long);
  18. void Benchmark(int);
  19. void ProjectionTest(int);
  20. void TempertureConverter(void);
  21. void TreeTest(int);
  22. Variable MakeTree(int);
  23.  
  24. /***************************************************************************
  25.  
  26.     Timing Functions
  27.  
  28. ****************************************************************************/
  29.  
  30. static long startTime;
  31.  
  32. #ifdef MACINTOSH    /***** Macintosh Timer *****/
  33.  
  34. #include <console.h>
  35. extern long Ticks : 0x16A;
  36.  
  37. long MillisecondClock()
  38. {
  39.     return (Ticks * 1000) / 60;
  40. }
  41.  
  42. /*
  43. #include <console.h>
  44. #include <profile.h>
  45. long MillisecondClock()
  46. {
  47.     return (VIA_ticks() * 128) / 100000;
  48. }
  49. */
  50.  
  51. #else            /***** Unix Timer *****/
  52.  
  53. #include <time.h>
  54. long MillisecondClock()
  55. {
  56.     struct timeval v;
  57.     struct timezone z;
  58.  
  59.     gettimeofday(&v,&z);
  60.     return (v.tv_sec * 1000) + (v.tv_usec / 1000);
  61. }
  62.  
  63. #endif
  64.  
  65. static void Start()
  66. {
  67.     startTime = MillisecondClock();
  68. }
  69.  
  70. static void Finish(milliseconds)
  71. long *milliseconds;
  72. {
  73.     *milliseconds = MillisecondClock() - startTime;
  74. }
  75.  
  76. /***************************************************************************
  77. *
  78. * This test builds and tests a Fahrenheit to Celcius temperature converter.
  79. *
  80. ****************************************************************************/
  81.  
  82. void TempertureConverter()
  83. {
  84.     Variable celcius, fahrenheit, t1, t2, nine, five, thirtyTwo;
  85.     Constraint addC, multC1, multC2;
  86.  
  87.     InitDeltaBlue();
  88.     celcius = Variable_Create("C", 0);
  89.     fahrenheit = Variable_Create("F", 0);
  90.     t1 = Variable_Create("t1", 1);
  91.     t2 = Variable_Create("t2", 1);
  92.     nine = Variable_CreateConstant("*const*", 9);
  93.     five = Variable_CreateConstant("*const*", 5);
  94.     thirtyTwo = Variable_CreateConstant("*const*", 32);
  95.  
  96.     printf("Before adding constraints:\n  ");
  97.     Variable_Print(celcius); printf(" = ");
  98.     Variable_Print(fahrenheit); printf("\n\n");
  99.  
  100.     printf("After adding constraints:\n  ");
  101.     multC1 = MultiplyC(celcius, nine, t1, S_required);
  102.     multC2 = MultiplyC(t2, five, t1, S_required);
  103.     addC = AddC(t2, thirtyTwo, fahrenheit, S_required);
  104.     Constraint_Print(multC1); printf("  ");
  105.     Constraint_Print(multC2); printf("  ");
  106.     Constraint_Print(addC); printf("  ");
  107.     Variable_Print(celcius); printf(" = ");
  108.     Variable_Print(fahrenheit); printf("\n\n");
  109.  
  110.     printf("Changing celcius to 0:\n  ");
  111.     Assign(celcius, 0);
  112.     Variable_Print(celcius); printf(" = ");
  113.     Variable_Print(fahrenheit); printf("\n\n");
  114.  
  115.     printf("Changing fahrenheit to 212:\n  ");
  116.     Assign(fahrenheit, 212);
  117.     Variable_Print(celcius); printf(" = ");
  118.     Variable_Print(fahrenheit); printf("\n\n");
  119.  
  120.     printf("Changing celcius to -40:\n  ");
  121.     Assign(celcius, -40);
  122.     Variable_Print(celcius); printf(" = ");
  123.     Variable_Print(fahrenheit); printf("\n\n");
  124.  
  125.     printf("Changing fahrenheit to 70:\n  ");
  126.     Assign(fahrenheit, 70);
  127.     Variable_Print(celcius); printf(" = ");
  128.     Variable_Print(fahrenheit); printf("\n\n");
  129. }
  130.  
  131. /* This is how to assign to constrained variables. */
  132. static void Assign(v, newValue)
  133. Variable v;
  134. long newValue;
  135. {
  136.     Constraint    editC;
  137.     long     msecs;
  138.     List    plan;
  139.  
  140.     editC = EditC(v, S_required);
  141.     if (SATISFIED(editC)) {
  142.     v->value = newValue;
  143.     plan = ExtractPlanFromConstraint(editC);
  144.     ExecutePlan(plan);
  145.     List_Destroy(plan);
  146.     }
  147.     DestroyConstraint(editC);
  148. }
  149.  
  150. /***************************************************************************
  151. *
  152. * This is the standard DeltaBlue benchmark. A long chain of equality
  153. * constraints is constructed with a stay constraint on one end. An edit
  154. * constraint is then added to the opposite end and the time is measured for
  155. * adding and removing this constraint, and extracting and executing a
  156. * constraint satisfaction plan. There are two cases. In case 1, the added
  157. * constraint is stronger than the stay constraint and values must propagate
  158. * down the entire length of the chain. In case 2, the added constraint is
  159. * weaker than the stay constraint so it cannot be accomodated. The cost in
  160. * this case is, of course, very low. Typical situations lie somewhere between
  161. * these two extremes.
  162. *
  163. ****************************************************************************/
  164.  
  165. static void Benchmark(n)
  166. int n;
  167. {
  168.     long     msecs, i;
  169.     char    name[20];
  170.     Variable    prev, v, first, last;
  171.     Constraint    editC;
  172.     List        plan;
  173.  
  174.     InitDeltaBlue();
  175.     prev = first = last = NULL;
  176.  
  177.   Start();
  178.     for (i = 0; i < n; i++) {
  179.     sprintf(name, "v%ld", i);
  180.     v = Variable_Create(name, 0);
  181.     if (prev != NULL) {
  182.         EqualsC(prev, v, S_required);
  183.     }
  184.     if (i == 0) first = v;
  185.     if (i == (n-1)) last = v;
  186.     prev = v;
  187.     }
  188.   Finish(&msecs);
  189.     printf("\n%ld msecs to add %d constraints.\n", msecs, n);
  190.     StayC(last, S_default);
  191.  
  192.   Start();
  193.     editC = EditC(first, S_strongDefault);
  194.   Finish(&msecs);
  195.     printf("Add Constraint (case 1): %ld msecs.\n", msecs);
  196.  
  197.   Start();
  198.     plan = ExtractPlanFromConstraint(editC);
  199.   Finish(&msecs);
  200.     printf(
  201.         "Make Plan (case 1): %ld msecs (plan is length %d).\n",
  202.         msecs, List_Size(plan));
  203.  
  204.   Start();
  205.     for (i = 0; i < 100; i++) {
  206.     ExecutePlan(plan);
  207.     }
  208.   Finish(&msecs);
  209.     printf("Execute Plan (case 1): %.3f msecs.\n", msecs / 100.0);
  210.     List_Destroy(plan);
  211.  
  212.   Start();
  213.     DestroyConstraint(editC);
  214.   Finish(&msecs);
  215.     printf("Remove Constraint (case 1): %ld msecs\n", msecs);
  216.  
  217.   Start();
  218.     editC = EditC(first, S_weakDefault);
  219.   Finish(&msecs);
  220.     printf("Add Constraint (case 2): %ld msecs.\n", msecs);
  221.  
  222.   Start();
  223.     plan = ExtractPlanFromConstraint(editC);
  224.   Finish(&msecs);
  225.     printf(
  226.     "Make Plan (case 2): %ld msecs (plan is length %d).\n",
  227.     msecs, List_Size(plan));
  228.  
  229.   Start();
  230.     for (i = 0; i < 100; i++) {
  231.     ExecutePlan(plan);
  232.     }
  233.   Finish(&msecs);
  234.     printf("Execute Plan (case 2): %.3f msecs.\n", msecs / 100.0);
  235.     List_Destroy(plan);
  236.  
  237.   Start();
  238.     DestroyConstraint(editC);
  239.   Finish(&msecs);
  240.     printf("Remove Constraint (case 2): %ld msecs\n", msecs);
  241.  
  242.   Start();
  243.     editC = EditC(last, S_strongDefault);
  244.   Finish(&msecs);
  245.     printf("Add Constraint (case 3): %ld msecs.\n", msecs);
  246.  
  247.   Start();
  248.     plan = ExtractPlanFromConstraint(editC);
  249.   Finish(&msecs);
  250.     printf(
  251.     "Make Plan (case 3): %ld msecs (plan is length %d).\n",
  252.     msecs, List_Size(plan));
  253.  
  254.   Start();
  255.     for (i = 0; i < 100; i++) {
  256.     ExecutePlan(plan);
  257.     }
  258.   Finish(&msecs);
  259.     printf("Execute Plan (case 3): %.3f msecs.\n", msecs / 100.0);
  260.     List_Destroy(plan);
  261.  
  262.   Start();
  263.     DestroyConstraint(editC);
  264.   Finish(&msecs);
  265.     printf("Remove Constraint (case 3): %ld msecs\n\n", msecs);
  266.  
  267. }
  268.  
  269. /***************************************************************************
  270. *
  271. * This test constructs a two sets of variables related to each other by a
  272. * simple linear transformation (scale and offset). The time is measured to
  273. * change a variable on either side of the mapping and to change the scale or
  274. * offset factors. It has been tested for up to 2000 variable pairs.
  275. *
  276. ****************************************************************************/
  277.  
  278. static void ProjectionTest(n)
  279. int n;
  280. {
  281.     Variable    src, scale, offset, dest;
  282.     long     msecs, i;
  283.     char    name[20];
  284.  
  285.     InitDeltaBlue();
  286.  
  287.   Start();
  288.     scale = Variable_Create("scale", 10);
  289.     offset = Variable_Create("offset", 1000);
  290.  
  291.     for (i = 1; i <= n; i++) {
  292.     /* make src and dest variables */
  293.     sprintf(name, "src%ld", i);
  294.     src = Variable_Create(name, i);
  295.     sprintf(name, "dest%ld", i);
  296.     dest = Variable_Create(name, i);
  297.  
  298.     /* add stay on src */
  299.     StayC(src, S_default);
  300.  
  301.     /* add scale/offset constraint */
  302.     ScaleOffsetC(src, scale, offset, dest, S_required);
  303.     }
  304.   Finish(&msecs);
  305.     printf("\nSetup time for %d points: %ld msecs.\n", n, msecs);
  306.  
  307.     Change(src, 17);
  308.     Change(dest, 1050);
  309.     Change(scale, 5);
  310.     Change(offset, 2000);
  311. }
  312.  
  313. static void Change(v, newValue)
  314. Variable v;
  315. long newValue;
  316. {
  317.     Constraint    editC;
  318.     long     i, msecs;
  319.     List    plan;
  320.  
  321.     printf("Changing %s...\n", v->name);
  322.   Start();
  323.     editC = EditC(v, S_strongDefault);
  324.   Finish(&msecs);
  325.     printf("  Adding Constraint: %ld msecs.\n", msecs);
  326.  
  327.   Start();
  328.     plan = ExtractPlanFromConstraint(editC);
  329.   Finish(&msecs);
  330.     printf("  Making Plan (length: %d): %ld msecs.\n", List_Size(plan), msecs);
  331.  
  332.   Start();
  333.     v->value = newValue;
  334.     for (i = 0; i < 100; i++) {
  335.     ExecutePlan(plan);
  336.     }
  337.   Finish(&msecs);
  338.     printf("  Executing Plan: %.3f msecs.\n", msecs / 100.0);
  339.     List_Destroy(plan);
  340.  
  341.   Start();
  342.     DestroyConstraint(editC);
  343.   Finish(&msecs);
  344.     printf("  Removing Constraint: %ld msecs\n", msecs);
  345. }
  346.  
  347. /***************************************************************************
  348. *
  349. * This test constructs a full binary tree of add constraints of the given
  350. * depth and then measures the time to change the root variable. Log(depth)
  351. * constraints must be traversed. DeltaBlue chooses an arbitrary path to a
  352. * leaf of the tree.
  353. *
  354. ****************************************************************************/
  355.  
  356. extern List allVariables;
  357.  
  358. static void TreeTest(depth)
  359. int depth;
  360. {
  361.     Variable root;
  362.     long msecs;
  363.  
  364.     InitDeltaBlue();
  365.     printf("Adder tree of depth %d\n", depth);
  366.  
  367.   Start();
  368.     root = MakeTree(depth);
  369.   Finish(&msecs);
  370.     /* Note: with stays, there is one constraint per variable */
  371.     printf(
  372.     "%d constraints added in %ld msecs.\n",
  373.     List_Size(allVariables), msecs);
  374.     Change(root, 17);
  375.     printf("\n");
  376. }
  377.  
  378. /* returns the root variable of an adder tree of the given depth */
  379. static Variable MakeTree(depth)
  380. int depth;
  381. {
  382.     Variable root, left, right;
  383.  
  384.     if (depth <= 0) {
  385.     root = Variable_Create("leaf", 1);
  386.     StayC(root, S_default);
  387.     } else {
  388.     root = Variable_Create("nonleaf", 1);
  389.     left = MakeTree(depth - 1);
  390.     right = MakeTree(depth - 1);
  391.     AddC(left, right, root, S_required);
  392.     }
  393.     return root;
  394. }
  395.  
  396. main()
  397. {
  398.     char **junk;
  399.  
  400. #ifdef MACINTOSH
  401.     ccommand(&junk);
  402.     printf("Macintosh Delta Blue Tests\n");
  403. #else
  404.     printf("DECStation Delta Blue Tests\n");
  405. #endif
  406.  
  407.     printf("Size of List is %d\n", sizeof(ListStruct));
  408.     printf("Size of Variable is %d\n", sizeof(VariableStruct));
  409.     printf("Size of Constraint is %d\n\n", sizeof(ConstraintStruct));
  410.  
  411.     TempertureConverter();
  412.     TreeTest(10);
  413.     Benchmark(50);
  414.     Benchmark(100);
  415.     Benchmark(200);
  416.     Benchmark(400);
  417.     Benchmark(800);
  418.     ProjectionTest(250);
  419.     ProjectionTest(500);
  420.     ProjectionTest(1000);
  421.     ProjectionTest(2000);
  422. }